package leetcode_600;

/**
 *@author 周杨
 *ContinuousSubarraySum_523 给定一个数组和一个k 判断在数组里是否存在一个子数组的和 能整除k
 *describe:用动态规划 AC 19%
 *2018年9月10日 上午11:48:58
 */
public class ContinuousSubarraySum_523 {
	 /**
	 * describe:动态规划记录i-j的sum 空间超时
	 * 2018年9月10日 上午11:42:01
	 */
	public boolean checkSubarraySum1(int[] nums, int k) {
	     if(nums.length<2)
	    	 return false;
	     if(k==0) {//是0的倍数 
	    	 for(int i=1;i<nums.length;++i) {
	    		 if(nums[i]==0&&nums[i-1]==0)
	    			 return true;
	    	 }
	    	 return false;
	     }
	     int dp[][]=new int[nums.length][nums.length];
	     dp[0][0]=nums[0];
	     for(int i=1;i<nums.length;++i) {
	    	 dp[i][i]=nums[i];
	    	 for(int j=0;j<i;++j) {
	    		 int now=dp[j][i-1]+nums[i];
	    		 if(now%k==0)
	    			 return true;
	    		 dp[j][i]=now;
	    		 }
	     }
	     return false;
	 }
	
	/**
	 * describe:动态规划 降维 AC 19%
	 * 2018年9月10日 上午11:48:44
	 */
	public boolean checkSubarraySum(int[] nums, int k) {
	     if(nums.length<2)
	    	 return false;
	     if(k==0) {//是0的倍数 
	    	 for(int i=1;i<nums.length;++i) {
	    		 if(nums[i]==0&&nums[i-1]==0)
	    			 return true;
	    	 }
	    	 return false;
	     }
	     int dp[]=new int[nums.length];//每次更新dp[j]到i的总和
	     dp[0]=nums[0];
	     for(int i=1;i<nums.length;++i) {
	    	 dp[i]=nums[i];
	    	 for(int j=0;j<i;++j) {
	    		 int now=dp[j]+nums[i];
	    		 if(now%k==0)
	    			 return true;
	    		 dp[j]=now;
	    	 }
	     }
	     return false;
	 }
}
